package _线性;

import java.util.*;

public class _栈 {
    //20 ：有效的括号 https://leetcode.cn/problems/valid-parentheses/
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{')
                stack.push(chars[i]);
            else {
                // 右边有多的,栈里面已经没有能和右字符匹配的
                if (stack.isEmpty()) return false;
                if ((chars[i] == ')' && stack.peek() == '(') || (chars[i] == ']' && stack.peek() == '[') ||
                        (chars[i] == '}' && stack.peek() == '{'))
                    stack.pop();
                    // 左右没匹配上
                else return false;
            }
        }
        // 左边有多的
        return stack.isEmpty();
    }

    // 739：每日温度：https://leetcode.cn/problems/daily-temperatures/description/
    // 返回一个数组 answer ，表示下一个更高温度出现在几天后
    // 输入: [73,74,75,71,69,72,76,73]
    // 输出: [1, 1, 4, 2, 1, 1, 0, 0]
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>(); // 存索引
        // 栈中存放的是递减温度对应的索引；
        // 如果当前温度比栈顶大，说明“栈顶那天”遇到更高温度；(出栈并更新答案)
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                res[prev] = i - prev;
            }
            stack.push(i);
        }
        return res;
    }

    // 496. 下一个更大元素 I：https://leetcode.cn/problems/next-greater-element-i/
    // 感觉最重要的是要搞清楚要 使用哪些数据结构
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // map 保存每个元素的 下一个更大元素。（存元素）
        Map<Integer, Integer> map = new HashMap<>();
        // st 维护一个递减栈，保存的是 nums2 中尚未找到“下一个更大元素”的元素。
        Stack<Integer> st = new Stack<>();
        for (int num : nums2) {
            while (!st.isEmpty() && num > st.peek()) {
                map.put(st.pop(), num);
            }
            st.push(num);
        }
        // 遍历一遍nums1，从map中获取结果
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}
